package swardToOffer.regularExpressions;

/**
 * @Author ChanZany
 * @Date 2021/5/21 9:29
 * @Version 1.0
 * 面试题19：正则表达式匹配
 * 题目：请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'
 * 表示任意一个字符，而'*'表示它【前面的字符】可以出现任意次（含0次）。在本题
 * 中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"
 * 和"ab*ac*a"匹配，但与"aa.a"及"ab*a"均不匹配。
 * <p>
 * str: aaa -> aa
 * pat: a.a -> .a
 * <p>
 * str: aaa ->aaa
 * pat: b*aa->aa
 * <p>
 * str: aaa ->aa
 * pat: a*aa->aa or a*aa
 */
public class RegularExpressions {

    boolean match(String str,String pattern){
        if (str.length() == 0 || pattern.length()==0) return false;
        char[] ch1 = str.toCharArray();
        char[] ch2 = pattern.toCharArray();
        return matchCore(ch1,0,ch2,0);
    }

    boolean matchCore(char[] str, int idxStr, char[] pattern, int idxPat) {
        if (idxStr == str.length - 1 && idxPat == pattern.length - 1) return true;
        if (idxStr != str.length - 1 && idxPat >= pattern.length - 1) return false;
        if (idxStr>str.length-1 || idxPat>pattern.length-1) return false;
        if (pattern[idxPat + 1] == '*') {
            if (pattern[idxPat] == str[idxStr] || (pattern[idxPat] == '.' && idxStr != str.length - 1)) {
                return matchCore(str, idxStr + 1, pattern, idxPat + 2) //认为'a*'=='a'
                        || matchCore(str, idxStr + 1, pattern, idxPat) //认为'a*' ='aa*'
                        || matchCore(str, idxStr, pattern, idxPat + 2); // 认为'a*'=''
            } else {
                return matchCore(str, idxStr, pattern, idxPat + 2); //只能跳过'b*'
            }
        }
        if (str[idxStr] == pattern[idxPat] || (pattern[idxPat] == '.' && idxStr != str.length - 1))
            return matchCore(str, idxStr + 1, pattern, idxPat + 1);
        return false;
    }

    public static void main(String[] args) {
        RegularExpressions Main = new RegularExpressions();
        System.out.println(Main.match("aaa", "a.a"));
        System.out.println(Main.match("aaa", "ab*ac*a"));
        System.out.println(Main.match("aba", "ab*ac*a"));
        System.out.println(Main.match("acadasdad", "a.*d"));
    }
}
